package DFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution93 {


    public static void main(String[] args) {
        String s = "19216811";
        String substring = s.substring(0, 0);
        System.out.println(restoreIpAddresses(s));
    }


    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        dfs(s, 0, 1, s.substring(0, 0), res);
        return res;
    }

    public static void dfs(String s, int index, int level, String chain, List<String> res) {
        if (level == 5 || index == s.length() - 1) {
            System.out.println(chain);
            if (Integer.parseInt(s.substring(index)) < 255) {
                res.add(chain);
            }
            return;
        }

        for (int i = index; i < s.length(); i++) {
            String substring = s.substring(index, i);
            if ("".equals(substring)) {
                continue;
            }
            if (Integer.parseInt(substring) > 255) {
                return;
            }
            if (chain.equals("")) {
                chain = chain + substring;

            } else {
                chain = chain + "." + substring;

            }
            dfs(s, index + 1, i + 1, chain, res);
            chain = chain.replace("." + substring, "");
        }
    }


}
